import java.util.*;
//236
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null ||  p == root || q == root){
            return root;
        }
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if(l != null && r != null){
            return root;
        }
        if(l != null)
            return l;
        return r;
    }
}
//235
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == p || root == q) return root;
        if(q.val < root.val && p.val < root.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        if(q.val > root.val && p.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}
//17
class Solution {
    public static String[] a = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    private List<String> ans = new ArrayList();
    private char[] digits,path;
    public List<String> letterCombinations(String digits) {
        this.digits = digits.toCharArray();
        path = new char[digits.length()];
        if(digits.length() == 0) return ans;
        dfs(0,digits);
        return ans;
    }
    private void dfs(int i, String digits){
        if(i == digits.length()){
            ans.add(new String(path));
            return;
        }
        for(char c: a[this.digits[i]-'0'].toCharArray()){
            path[i] = c;
            dfs(i+1,digits);
        }
    }
}
public class Test {
}
